The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent the work is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.
In communication systems, channel noise may cause transmission errors between a source and a receiver. Error correction coding (ECC) techniques may detect and correct channel transmission errors. Low-density parity-check (LDPC) codes are examples of ECC block codes that may provide coding gains to improve performance.
A coding gain is an amount of additional noise that an ECC coded system may handle compared to an uncoded system. In other words, the coding gain may enable the ECC coded system to transmit at a lower bit error rate (BER) than an uncoded system. Therefore, in applications in which transmit power may be limited, the coding gains of LDPC codes may make the difference between reliable and unreliable communication.
Referring now to FIG. 1, a functional block diagram illustrating a conventional communication system 10 is shown. The communication system 10 may include an LDPC encoder 12, a modulator 14, a channel 16, a demodulator 18, and an iterative LDPC decoder 20. The iterative LDPC decoder 20 may include a channel detector 22, such as a soft-output Viterbi algorithm (SOVA) detector, and an LDPC decoder 24.
Using a given LDPC code, the LDPC encoder 12 encodes a stream of datawords (u) from a source. A dataword may refer to a group of binary data bits that is suitable for input to the LDPC encoder 12. The LDPC encoder 12 outputs a stream of codewords (c) which may be in the form of binary data. A codeword may refer to a group of bits generated by the LDPC encoder 12 based on an input dataword.
LDPC codes are block codes and thus an LDPC code may be represented by an (M×N) parity-check matrix (H) that includes M rows and N columns. M may represent a number of constraints, such as parity-check equations. N may represent a number of bits. Entries of the parity-check matrix may be a one or a zero. For example, a bit vn participates in a constraint cm if Hm,n=1.
The modulator 14 modulates the frequency, amplitude, and/or phase of the stream of codewords to generate a transmitted signal (w) that includes a modulated communication or storage signal. For example, the channel 16 may include a storage medium, such as a magnetic storage medium, an optical storage medium, or an electrical storage medium. The channel 16 may also include a communication channel. The channel 16 provides a received signal (w′), which may represent the transmitted signal corrupted by noise (n) or other interference.
The demodulator 18 demodulates the received signal and provides an initial estimate signal (r′) of the stream of codewords. The channel detector 22 of the iterative LDPC decoder 20 receives the initial estimate signal, which may be based on hard information in blocks of data. The initial estimate signal may include corrupted bits. Hard information represents hard decisions on whether data bits are ones or zeros. In other words, a hard decision for a bit may be either a one or a zero.
The channel detector 22 may generate soft information via a soft decision that is based on the initial estimate signal and data from the channel 16. Soft information represents soft decisions on whether data bits are ones or zeros. In other words, a soft decision for a bit may be a real number that represents a probability or a likelihood of belief that the bit is a one or a zero.
For example, the soft information may be log-likelihood ratios (LLRs). An LLR is equal to the logarithm of the probability (Pr) that a bit is equal to one divided by the probability that the bit is equal to zero. In other words, the LLR of a bit v may be defined as:
      LLR    ⁡          (      v      )        =      log    ⁢                  ⁢                            Pr          ⁡                      (                          v              =              1                        )                                    Pr          ⁡                      (                          v              =              0                        )                              .      
The sign of the LLR indicates a most likely value of the bit v. For example, a negative LLR relates to a higher probability of the bit being a 0. The value of the LLR indicates certainty of the value. For example, a larger value LLR relates to a higher certainty of the bit being a 0 or a 1.
For example, the channel detector 22 may generate the soft information based on the Viterbi algorithm. The channel detector 22 may also generate the soft information based on channel factors such as a type of modulation used by the modulator 14 and channel parameters such as additive white Gaussian noise (AWGN).
The LDPC decoder 24 receives the soft information and may attempt satisfying M parity-check equations of the parity-check matrix using the soft information. However, if one or more of the parity-check constraints are not satisfied, the LDPC 24 decoder may generate feedback information. For example, a message-passing algorithm such as a sum-product algorithm may be used to generate the feedback information. And in such an example, feedback messages from check nodes may be summed to generate the feedback information for a bit.
The channel detector 22 receives the feedback information and may update the soft information from the channel based on the feedback information. For example, the channel detector 22 may sum the soft information and the feedback information to generate updated soft information. The LDPC decoder 24 receives the updated soft information, and the process repeats.
For example, the iterative LDPC decoder 20 may repeat this process for numerous iterations to decode an entire block of data. The iterative LDPC decoder 20 may continue until a valid codeword is found that satisfies all M parity-check equations. The iterative LDPC decoder 20 may also continue until an allotted time has elapsed or when a certain number of iterations have occurred.
The iterative LDPC decoder 20 generates an estimate signal (r) based on the soft information and the iterative decoding process. The estimate signal represents an estimate of the original transmitted stream of datawords. For example, the estimate signal may include the most likely datawords. The estimate signal may also include the original stream of datawords if no error exists.
Referring now to FIG. 2A, the LDPC decoder 24 may include a plurality of nodes 30. The nodes 30 illustrate the iterative message-passing process between variable and check nodes (described above) which is used by a typical LDPC decoder 24. For example, the nodes 30 represents the following parity-check matrix H:
  H  =            [                                    1                                1                                1                                0                                0                                0                                                1                                0                                0                                1                                1                                0                                                0                                1                                1                                0                                0                                1                                                0                                0                                0                                1                                1                                1                              ]        .  
The nodes 30 may include check nodes c0 (34-0), c1 (34-1), c2 (34-2), and c3 (34-3) (collectively referred to as check nodes 34). The nodes 30 may also includes variable nodes v0 (36-0), v1 (36-1), v2 (36-2), v3 (36-3), v4 (36-4), and v5 (36-5) (collectively referred to as variable nodes 36).
Referring now to FIG. 2B, the relationship between the check nodes 34, the variable nodes 36, and the parity-check matrix H is shown. The variable nodes 36 correspond to the N columns of the parity-check matrix H. The check nodes 34 correspond to the M rows of the parity-check matrix H.
The interacting nodes 30 may be referred to as a bipartite graph because no nodes of the same type (i.e., variable nodes and check nodes) are connected to each other. Communication lines connect check nodes 34 to variable nodes 36. In other words, one of the check nodes 34 is connected to one of the variable nodes 36 if the corresponding entry in the parity-check matrix is a one. For example, check node c0 (34-0) is connected to variable node v0 (36-0) because H0,0=1.
Information received from the channel 16 is communicated to the variable nodes 36 via the channel detector 22. The variable nodes 36 may pass the information up to the check nodes 34. For example, variable node v0 (36-0) may pass a message (i.e., channel information) to check nodes c0 (34-0) and c1 (34-1) because the nodes are connected.
The check nodes 34 may compute messages based on the information received from the variable nodes 36. For example, one of the check nodes 34 may compute a message by summing all messages received from variable nodes 36. The check nodes 34 may then pass the messages back to respective variable nodes 36.
For example, check node c0 (34-0) may compute a message by summing messages received from variable nodes v0 (36-0), v1 (36-1), and v2 (36-2) because the nodes are connected. Check node c0 (34-0) may also send the message back to variable nodes v0 (36-0), v1 (36-1), and v2 (36-2) because the nodes are connected.
The variable nodes 36 may then compute messages based on the messages received from the check nodes 34. For example, one of the variable nodes 36 may compute a message by summing all messages received from check nodes 36. For example, variable node v0 (36-0) may compute a feedback signal by summing messages received from check nodes c0 (34-0) and c1 (34-1) because the nodes are connected.
The check nodes 34 may send the feedback signals back to the channel detector 22. The channel detector 22 may generate updated soft information based on the feedback signals and the soft information. The LDPC decoder 24 then receives the updated soft information.
The iterative message-passing process may be repeated until a predetermined condition is satisfied. After the predetermined condition is satisfied, the iterative LDPC decoder 20 may generate and output an estimate signal r. For example, the iterative message-passing process may continue until a predetermined number of iterations have occurred or until all parity-check equations are satisfied. For example, the parity-check equations corresponding to the parity-check matrix H are:
            c      0        =                  v        0            +              v        1            +              v        2                        c      1        =                  v        0            +              v        3            +              v        4                        c      2        =                  v        1            +              v        2            +              v        5                        c      3        =                  v        3            +              v        4            +                        v          5                .            
Referring now to FIG. 3A, an exemplary variable node computation is shown. A variable node 38 receives an initial bit estimate (y), which may be an LLR, from a channel detector (not shown). The variable node 38 may also receive return messages x0, x1, and x2 from the different check nodes. The variable node 38 may generate return messages based on the received return messages and the initial bit estimate. For example, the variable node 38 may generate return messages for each check node by summing all of the other received messages, as shown in FIG. 3B.